﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MessageWorkflow.Graph.Algorithm
{
    // see: https://qir.kyushu-u.ac.jp/dspace/bitstream/2324/10751/1/2008-1.pdf
    sealed class TarjanAlgorithm<T>
    {
        class NodeInformation
        {
            public int Index;
            public int LowestLink;

            public NodeInformation(int index)
            {
                Index = index;
                LowestLink = index;
            }
        }

        private IGraph<T> _graph;
        private Dictionary<T, NodeInformation> _nodesInformation;
        private Stack<T> _handledNodes;
        private int _index;

        public TarjanAlgorithm(IGraph<T> graph)
        {
            this._graph = graph;
        }

        public IEnumerable<IEnumerable<T>> FindStronglyConnectedComponents()
        {
            // reset
            _nodesInformation = new Dictionary<T, NodeInformation>();
            _handledNodes = new Stack<T>();
            _index = 0;

            foreach (T node in _graph.Nodes)
            {
                // only take nodes which havent been indexed (and therefore have no information about them)
                if (!_nodesInformation.ContainsKey(node))
                {
                    IEnumerable<T> result = FindStronglyConnectedComponent(node).ToArray();
                    if (result.Any())
                    {
                        yield return result;
                    }
                }
            }
        }

        public IEnumerable<T> FindStronglyConnectedComponent(T node)
        {
            NodeInformation nodeInformation = new NodeInformation(_index);
            _nodesInformation[node] = nodeInformation;
            _index++;

            _handledNodes.Push(node);

            foreach (T successorNode in _graph.GetSuccessors(node))
            {
                if (!_nodesInformation.ContainsKey(successorNode))
                {
                    // this value has not been indexed, therefore go recursive on it
                    FindStronglyConnectedComponent(successorNode).ToArray();

                    NodeInformation successorNodeInformation = _nodesInformation[successorNode];
                    nodeInformation.LowestLink = Math.Min(nodeInformation.LowestLink, successorNodeInformation.LowestLink);
                }
                else if (_handledNodes.Contains(successorNode))
                {
                    // successornode is in the stack and therefore already has information associated with it
                    NodeInformation successorNodeInformation = _nodesInformation[successorNode];

                    if (successorNodeInformation.Index < nodeInformation.Index)
                    {
                        nodeInformation.LowestLink = System.Math.Min(successorNodeInformation.Index, nodeInformation.LowestLink);
                    }
                }
            }

            if (nodeInformation.Index == nodeInformation.LowestLink)
            {
                T current = _handledNodes.Pop();

                while (!object.Equals(current, node)) 
                {
                    current = _handledNodes.Pop();

                    yield return current;
               } 
            }
        }
    }
}
